﻿#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
/*
==========================================================
给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

 

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/majority-element
==========================================================
*/


//法1，快速排序后，然后取下标为n/2的值
// 
// 
//int comp(const void* p1, const void* p2)
//{
//	return ((*(int*)p1) - (*(int*)p2));
//}
//int majorityElement(int* nums, int numsSize)
//{
//	qsort(nums, numsSize, sizeof(int), comp);
//	return nums[numsSize / 2];
//}
// 
// 
// 



//法2，摩尔投票法(同归于尽)
//int majorityElement(int* nums, int numsSize)
//{
//	//假设相同的数是一个阵营，进行PK
//	//由于多数元素至少比其他元素总和还多1个，所以剩下的一定是多数元素
//
//	//抵消阶段
//	int count = 1;
//	int major = nums[0];
//	for (int i = 1; i < numsSize; i++)
//	{
//		if (count != 0)
//		{
//			if (nums[i] == major)
//			{
//				count++;
//			}
//			else
//			{
//				count--;
//			}
//		}
//		else
//		{
//			major = nums[i];
//			count = 1;
//		}
//	}
//	
//	//检验阶段
//	int n = 0;
//	for (int i = 0; i < numsSize; i++)
//	{
//		if (major == nums[i])
//		{
//			n++;
//		}
//	}
//	if (n > numsSize / 2)
//	{
//		return major;
//	}
//	else
//	{
//		return -1;
//	}
//}
